package 路径总和;

public class Solution {
    /*
    给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根
    节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum。
    如果存在，返回 true ；否则，返回 false。叶子节点 是指没有子节点的节点
    */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // 递归法
        // 1.参数：父节点，从根节点到父节点的sum，返回值:boolean是否存在这种路径
        // 2.终止条件：遇到叶子节点
        // 3.单层递归的逻辑：采用（根 左 右）遍历，且记录从根节点到目前节点的sum。只要遇到叶子节点，就比较sum值和目标值是否一样
        // 如果一致，就返回true，不一致就返回false。只要递归中遇到一个true就一致返回true即可
        // 如果整个树遍历结束没有从return true的口弹出去，就需要返回false为最终结果
        if(root == null)
            return false;
        return hasPathSumJ(root, targetSum, root.val);
    }

    public boolean hasPathSumJ(TreeNode root, int targetSum, int sum) {
        //根
        if (root.left == null && root.right == null) {
            return sum == targetSum;
        }
        // 左
        if (root.left != null) {
            sum += root.left.val;
            if (hasPathSumJ(root.left, targetSum, sum)) return true;
            sum -= root.left.val;
        }
        // 右
        if (root.right != null) {
            sum += root.right.val;
            if (hasPathSumJ(root.right, targetSum, sum)) return true;
            sum -= root.right.val;
        }
        return false;
    }
}
